/**********************************************************************
*  Copyright (c) 2007 - Victor Jacobs - victor.jacobs@gmail.com
*
*  Permission is hereby granted, free of charge, to any person
*  obtaining a copy of this software and associated documentation
*  files (the "Software"), to deal in the Software without
*  restriction, including without limitation the rights to use,
*  copy, modify, merge, publish, distribute, sublicense, and/or sell
*  copies of the Software, and to permit persons to whom the
*  Software is furnished to do so, subject to the following
*  conditions:
*
*  The above copyright notice and this permission notice shall be
*  included in all copies or substantial portions of the Software.
*
*  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
*  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
*  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
*  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
*  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
*  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
*  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
*  OTHER DEALINGS IN THE SOFTWARE.
**********************************************************************/

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Vj.MathLibrary.Binary
{
    public class BitList
    {
        private Bit[] bitList;

        #region Constructors

        public BitList()
        {
            bitList = new Bit[8];

            for (int i = 0; i < 8; i++)
            {
                bitList[i] = new Bit(0);
            }
        }

        public BitList(int size)
        {
            if (size < 0)
                throw new ArgumentOutOfRangeException();

            bitList = new Bit[size];

            for (int i = 0; i < size; i++)
                bitList[i] = new Bit(0);
        }

        public BitList(int[] intArray)
        {
            if (intArray == null)
                throw new ArgumentNullException();

            bitList = new Bit[intArray.Length];

            for (int i = 0; i < intArray.Length; i++)
                bitList[i] = new Bit(0);

            for (int i = 0; i < intArray.Length; i++)
            {
                if (intArray[i] != 0 && intArray[i] != 1)
                    throw new ArgumentException("Bits should only be zero or one.");

                bitList[i].IntValue = intArray[i];
            }
        }

        public BitList(bool[] boolArray)
        {
            if (boolArray == null)
                throw new ArgumentNullException();

            bitList = new Bit[boolArray.Length];

            for (int i = 0; i < boolArray.Length; i++)
                bitList[i] = new Bit(0);

            for (int i = 0; i < boolArray.Length; i++)
            {
                bitList[i].BoolValue = boolArray[i];
            }
        }

        #endregion

        #region Propreties

        public int Length
        {
            get { return bitList.Length; }
            set
            {
                if (value < 0)
                    throw new ArgumentException();

                if (value <= this.Length)
                    throw new InvalidOperationException("Length can only increase.");

                Bit[] newBitList = new Bit[value];
                for (int i = 0; i < newBitList.Length; i++)
                    newBitList[i] = new Bit(0);

                for (int i = 0; i < this.Length; i++)
                    newBitList[i].IntValue = this[i].IntValue;

                for (int i = this.Length; i < value; i++)
                    newBitList[i].IntValue = 0;

                this.bitList = newBitList;
            }
        }

        public Bit this[int index]
        {
            get { return bitList[index]; }
            set { bitList[index] = value; }
        }

        public int Integer
        {
            get
            {
                if ((long)Math.Pow(2, this.Length)-1 > (long)int.MaxValue)
                    throw new OverflowException("Integer equivalent is to large for int value type.");

                int result = 0;

                for (int i = 0; i < this.Length; i++)
                {
                    if (this[i].IntValue == 1)
                        result += (int)Math.Pow(2, i);
                }

                return result;
            }
            set
            {
                if (value < 0)
                    throw new ArgumentException("Value must be positive.");

                int maxLength = (int)Math.Log(value, 2);
                
                List<Bit> tmpBitList = new List<Bit>();
                int intValue = value;

                while (intValue > 0)
                {
                    tmpBitList.Add(new Bit(intValue % 2));
                    intValue = intValue / 2;
                }

                Bit[] returnList = tmpBitList.ToArray();
                this.bitList = returnList;
            }
        }

        public bool GetBit(int index)
        {
            return bitList[index].BoolValue;
        }

        public void SetBit(int index, bool value)
        {
            bitList[index].BoolValue = value;
        }
        
        public override string ToString()
        {
            if (this.Length == 0)
                return "{ }";

            string output = "{ ";

            for (int i = this.Length - 1; i > 0; i--)
                output += this[i].ToString() + ", ";

            output += this[0] + " }";

            return output;
        }

        #endregion

        #region Trim, Reverse, Flip, Randomize

        // Trim leading zeros.
        public BitList GetTrimmed()
        {
            if (this.Length == 0)
                return this;
            
            int maxBitIndex = 0;

            for (int i = bitList.Length-1; i >= 0; i--)
            {
                if (bitList[i].IntValue == 1)
                {
                    maxBitIndex = i;
                    break;
                }
            }

            if (maxBitIndex == 0)
                return new BitList(0);

            int[] tmpList = new int[maxBitIndex+1];

            for (int i = 0; i < maxBitIndex+1; i++)
                tmpList[i] = bitList[i].IntValue;

            return new BitList(tmpList);
        }

        public BitList GetReversed()
        {
            BitList tmpList = new BitList(this.bitList.Length);

            for (int i = 0; i < bitList.Length; i++)
            {
                tmpList[bitList.Length - 1 - i] = bitList[i];
            }

            return tmpList;
        }

        public BitList GetFlipped()
        {
            BitList tmpList = new BitList(this.bitList.Length);

            for (int i = 0; i < bitList.Length; i++)
            {
                tmpList[i] = !bitList[i];
            }

            return tmpList;
        }

        public BitList GetRandomized()
        {
            BitList tmpList = new BitList(this.bitList.Length);

            for (int i = 0; i < bitList.Length; i++)
                tmpList.SetBit(i, RandomGrabber.NextBoolean());

            return tmpList;
        }

        public void Trim()
        {
            if (this.Length == 0)
                return;

            int maxBitIndex = 0;

            for (int i = bitList.Length - 1; i >= 0; i--)
            {
                if (bitList[i].IntValue == 1)
                {
                    maxBitIndex = i;
                    break;
                }
            }

            if (maxBitIndex == 0)
            {
                bitList = new Bit[0];
                return;
            }

            Bit[] tmpList = new Bit[maxBitIndex + 1];
            
            for (int i = 0; i < maxBitIndex + 1; i++)
            {
                tmpList[i] = new Bit();
                tmpList[i].BoolValue = bitList[i].BoolValue;
            }

            bitList = tmpList;
        }

        public void Reverse()
        {
            Bit[] tmpList = new Bit[this.bitList.Length];

            if (tmpList.Length > 1) // no need to reverse single bit
            {
                for (int i = 0; i < bitList.Length; i++)
                {
                    tmpList[bitList.Length - 1 - i] = new Bit();
                    tmpList[bitList.Length - 1 - i].BoolValue = bitList[i].BoolValue;
                }

                bitList = tmpList;
            }
        }

        public void Flip()
        {
            Bit[] tmpList = new Bit[this.bitList.Length];

            for (int i = 0; i < bitList.Length; i++)
            {
                tmpList[i] = new Bit();
                tmpList[i].BoolValue = !bitList[i].BoolValue;
            }

            bitList = tmpList;
        }

        public void Randomize()
        {
            Bit[] tmpList = new Bit[this.bitList.Length];

            for (int i = 0; i < bitList.Length; i++)
            {
                tmpList[i] = new Bit();
                tmpList[i].BoolValue = RandomGrabber.NextBoolean();
            }

            bitList = tmpList;
        }

        #endregion

        #region Bit Operations

        public static BitList XOR(BitList firstList, BitList secondList)
        {
            if (firstList == null || secondList == null)
                throw new ArgumentNullException();

            if (firstList.Length != secondList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(firstList.Length);

            for (int i = 0; i < firstList.Length; i++)
            {
                if (firstList[i].IntValue == 0 && secondList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 0 && secondList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public static BitList AND(BitList firstList, BitList secondList)
        {
            if (firstList == null || secondList == null)
                throw new ArgumentNullException();

            if (firstList.Length != secondList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(firstList.Length);

            for (int i = 0; i < firstList.Length; i++)
            {
                if (firstList[i].IntValue == 0 && secondList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 0 && secondList[i].IntValue == 1) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 1) { returnList[i].IntValue = 1; }
            }

            return returnList;
        }

        public static BitList OR(BitList firstList, BitList secondList)
        {
            if (firstList == null || secondList == null)
                throw new ArgumentNullException();

            if (firstList.Length != secondList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(firstList.Length);

            for (int i = 0; i < firstList.Length; i++)
            {
                if (firstList[i].IntValue == 0 && secondList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 0 && secondList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 1) { returnList[i].IntValue = 1; }
            }

            return returnList;
        }

        public static BitList NOR(BitList firstList, BitList secondList)
        {
            if (firstList == null || secondList == null)
                throw new ArgumentNullException();

            if (firstList.Length != secondList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(firstList.Length);

            for (int i = 0; i < firstList.Length; i++)
            {
                if (firstList[i].IntValue == 0 && secondList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 0 && secondList[i].IntValue == 1) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public static BitList NAND(BitList firstList, BitList secondList)
        {
            if (firstList == null || secondList == null)
                throw new ArgumentNullException();

            if (firstList.Length != secondList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(firstList.Length);

            for (int i = 0; i < firstList.Length; i++)
            {
                if (firstList[i].IntValue == 0 && secondList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 0 && secondList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (firstList[i].IntValue == 1 && secondList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public static BitList NOT(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (aList[i].IntValue == 0)
                    returnList[i].IntValue = 1;
                else
                    returnList[i].IntValue = 0;
            }

            return returnList;
        }


        public BitList XOR(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();

            if (this.Length != aList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (this[i].IntValue == 0 && aList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 0 && aList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public BitList AND(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();

            if (this.Length != aList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (this[i].IntValue == 0 && aList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 0 && aList[i].IntValue == 1) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 1) { returnList[i].IntValue = 1; }
            }

            return returnList;
        }

        public BitList OR(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();
            
            if (this.Length != aList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (this[i].IntValue == 0 && aList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 0 && aList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 1) { returnList[i].IntValue = 1; }
            }

            return returnList;
        }

        public BitList NOR(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();

            if (this.Length != aList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (this[i].IntValue == 0 && aList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 0 && aList[i].IntValue == 1) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 0) { returnList[i].IntValue = 0; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public BitList NAND(BitList aList)
        {
            if (aList == null)
                throw new ArgumentNullException();

            if (this.Length != aList.Length)
                throw new ArgumentException("Dimensions must match.");

            BitList returnList = new BitList(aList.Length);

            for (int i = 0; i < aList.Length; i++)
            {
                if (this[i].IntValue == 0 && aList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 0 && aList[i].IntValue == 1) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 0) { returnList[i].IntValue = 1; }
                else if (this[i].IntValue == 1 && aList[i].IntValue == 1) { returnList[i].IntValue = 0; }
            }

            return returnList;
        }

        public BitList NOT()
        {
            BitList returnList = new BitList(this.Length);

            for (int i = 0; i < this.Length; i++)
            {
                if (this[i].IntValue == 0)
                    returnList[i].IntValue = 1;
                else
                    returnList[i].IntValue = 0;
            }

            return returnList;
        }

        #endregion

        #region Binary-to-Gray, Gray-to-Binary

        // bin-to-gray
        public BitList ConvertToGrayCode()
        {
            //Let B[n:0] be the input array of bits in the usual binary representation, [0] being LSB
            //Let G[n:0] be the output array of bits in Gray code
            //G[n] = B[n]
            //for i = n-1 downto 0
            //    G[i] = B[i+1] XOR B[i]

            int length = this.Length;

            if (length == 0 || length == 1)
                return this;

            BitList returnedBitList = new BitList(length);
            
            returnedBitList[length - 1] = this[length - 1];

            for (int i = length - 2; i >= 0; i--)
                returnedBitList[i] = Bit.XOR(this[i+1], this[i]);

            return returnedBitList;
        }

        // gray-to-bin
        public BitList ConvertToBinary()
        {
            //Let G[n:0] be the input array of bits in Gray code
            //Let B[n:0] be the output array of bits in the usual binary representation
            //B[n] = G[n]
            //for i = n-1 downto 0
            //    B[i] = B[i+1] XOR G[i]

            int length = this.Length;

            if (length == 0)
                return new BitList(0);

            BitList returnedBitList = new BitList(length);
            returnedBitList[length - 1] = this[length - 1];

            for (int i = length - 2; i >= 0; i--)
                returnedBitList[i] = Bit.XOR(returnedBitList[i + 1], this[i]);

            return returnedBitList;
        }

        public static BitList GrayToBinaryConversion(BitList grayBitList)
        {
            //Let G[n:0] be the input array of bits in Gray code
            //Let B[n:0] be the output array of bits in the usual binary representation
            //B[n] = G[n]
            //for i = n-1 downto 0
            //    B[i] = B[i+1] XOR G[i]

            if (grayBitList == null)
                throw new ArgumentNullException();

            int length = grayBitList.Length;

            if (length == 0)
                return new BitList(0);

            BitList returnedBitList = new BitList(length);
            returnedBitList[length - 1] = grayBitList[length - 1];

            for (int i = length - 2; i >= 0; i--)
                returnedBitList[i] = Bit.XOR(returnedBitList[i + 1], grayBitList[i]);

            return returnedBitList;
        }

        public static BitList BinaryToGrayConversion(BitList binaryBitList)
        {
            //Let B[n:0] be the input array of bits in the usual binary representation, [0] being LSB
            //Let G[n:0] be the output array of bits in Gray code
            //G[n] = B[n]
            //for i = n-1 downto 0
            //    G[i] = B[i+1] XOR B[i]

            if (binaryBitList == null)
                throw new ArgumentNullException();

            int length = binaryBitList.Length;

            if (length == 0)
                return new BitList(0);

            BitList returnedBitList = new BitList(length);
            returnedBitList[length - 1] = binaryBitList[length - 1];

            for (int i = length - 2; i >= 0; i--)
                returnedBitList[i] = Bit.XOR(binaryBitList[i], binaryBitList[i + 1]);

            return returnedBitList;
        }

        #endregion
         
    }
}
